Speakers

Introduction to Column Generation and hybrid methods for Homecare Routing

In this session we will present the key concept of Column Generation and illustrate how it can be applied to Vehicle Routing. We will also discuss difference practical issues of Column Generation and pricing strategy such as Dynamic Programming and Constraint Programming. The second part of the class will address a practical routing problem which arises in the field of Homecare, where we will combine column generation and LNS.
Download the CG exercise sheet.

Do it yourself!

Mini-CP challenge! The participants will be challenged on a given problem both in term of modeling and implementation of a solution in their own standalone tool.

Resource Constraints for Scheduling

The goal of this tutorial is to give an overview of a key contribution of constraint programming to the domain of scheduling: efficient algorithms for reasoning about complex resources. I will first survey well known algorithms for propagating disjunctive and cumulative renewable resource constraints. In particular, the timetabling, edge-finding and energetic reasoning algorithms will be analyzed in depth. Then, less standard types of resources will be introduced, such as cache and capacity resources together with some algorithms to reason about them.

Characterizing the flexibility of an energy consumer and optimizing its usage: a multifaceted problem

The exploitation of flexibility in energy production and consumption is essential to avoid costly reinforcements of the power system and maintain security of supply while increasing the penetration of renewable (and intermittent) sources of energy. Let us focus on the "demand" side, i.e., on actors which are mostly consumers of energy: manufacturing plants, water networks, commercial buildings (or even elements in a building such as an HVAC (Heating, Ventilation and Air Conditioning) system, an elevator or a pool of elevators), and aggregations of those, such as a district. These actors use energy for their own needs, i.e., manufacture and deliver products to their own customers, deliver drinkable water to their customers, provide a comfortable work place to the employees and visitors of the building, etc. They may also produce energy, either as part of the process they manage (e.g., cogeneration in an industrial plant, elevator braking energy recovery) or with energy production resources installed for cost reduction and security reasons. Finally, they may also have energy storage resources, which could have been installed to build flexibility or for any other reason. Part or all of the stored energy capacity can then be used to reduce operational costs.

Incentives to reduce or shift energy consumption in time must be considered with respect to the main objectives (and other cost factors) of the consuming organization. The very first thing to do is to characterize the available or potential sources of flexibility and how they could be used to make gains in terms of energy, revenues and cost savings, or environmental impact.

• First, there may exist options for definitive savings of energy with no significant impact on the process for which the energy is used. In general, such savings will be doable provided they have an "acceptable" impact on the process or on its outcome. For example, the capacity to slightly dim lights in an elevator enables direct and definitive energy savings. Such dimming is acceptable if it does not occur too often.
• Delays in consumption are possible when a given activity can be delayed (or performed in advance) or, more generally, when savings are possible at a given time but at the expense of further consumption before or after this time. For example, if enough water is available in a water tower, one can delay for a while the pumping of water into the water tower. At some point, however, pumping will be needed to ensure the water tower gets enough water to serve the local customers. Similarly, highly consuming activities in a manufacturing plant might be avoided during a given interval of time, provided these activities are not time-critical and the corresponding products are available in stock. At some point, however, it will become necessary to perform these activities, and consume the corresponding amount of energy to replenish the stock.
• If energy storage (e.g., in batteries, in the form of hot water, etc.) is possible, then the stored energy can be used to provide an apparent consumption flexibility. For example, part of the energy stored in the battery of an elevator can be used to temporarily operate the elevator with no other impact on the elevator’s process.

Considered separately, such sources of flexibility induce very different optimization models: multi-criteria regulation; scheduling with energy resource constraints and costs; energy flow optimization. Things get more complex when these sources of flexibility coexist and when multiple actors, each with its own constraints and objectives, share the same energy network. Practical optimization problems will be presented, using examples from two European projects (Arrowhead and Ambassador) and from the two PhD theses of Chloé Desdouits "Reduction of electricity consumption peaks and optimization problems induced on the demand side" and Peter Pflaum "Energy management strategies for smart grids".

Consistency in search algorithms: consistency of the solution according to the computing power used

Many users are disappointed when two runs of the same solver sometimes do not return the same solution. This notion is often called the determinism of a solver or of an algorithm. But, many users are quite disappointed by the non consistency of a solution returned by a software according to the computing effort used by the software to find the solution. Many users are disappointed when a solution returned by software for a given time limit is not as good as a solution returned by the same software with a bigger time limit, Many users are disappointed when a parallel algorithm that uses 4 cores sometimes solves a problem faster than the same algorithm using 8 cores. In many cases, users expect a quality of a solution to evolve in relation with the computing power used to solve this solution. We discuss in this talk an extension of determinism we call consistency of an algorithm. We will show what is possible to do with sequential or parallel search algorithms that are an abstraction of search algorithms used to solve problems like CSP, SAT or MIP.

CP in a nutshell

On the Flinders Hamiltonian Cycle Problem Challenge

Placing virtual machines in a cloud under constraints

Private and public cloud data centers are platforms of choice to host a large scope of applications. Coupled with the use of Virtual Machines (VMs) to wrap the applications, they exhibit small operation costs thanks to workload consolidation. The VM scheduler is the cornerstone of a performant and profitable virtualized infrastructure. The provider bases his offering and the clients base their requirements on its features. Developing a VM scheduler is however a challenging task. Above all, the developer must overcome the theoretical foundations of the problem and their consequences over the problem scalability. He must also provide an architecture that is flexible enough to support the evolving requirements of the users. The quality of a scheduler might then always be the consequence of a good match between its reasoning capabilities, the infrastructure particularities and the workload profile. It might then be vain to look for the perfect pre-packaged VM scheduler and start to package its own.

In this talk, I will discuss about the open source VM scheduler BtrPlace. BtrPlace allows third party developers to enhance its reasoning capabilities and make it support new, possibly unique concerns. The flexibility and the reasoning capabilities of BtrPlace are granted by the extensive use of Constraint Programming and the Choco solver. During the talk, I will present the VM placement problem, its model and its implementation. I will also review the different design choices we made for the last ten years of development and their consequences in terms of capabilities and performance. BtrPlace is developed by the University of Nice Sophia Antipolis since 2011. It is a complete rewrite of Entropy, the project initiated in 2006 at the Mines de Nantes. Despite being initially a research prototype, BtrPlace is used in production, because of its flexibility. Nutanix, a provider of entreprise clusters uses it in thousands of private clouds worldwide to mitigate local load spikes.